import functools


class Solution(object):
    def splitArraySameAverage(self, nums):
        n = len(nums)
        total = sum(nums)
        nums = [num * n - total for num in nums]
        A = nums[: n // 2]
        B = nums[n // 2:]
        a_set = set()
        b_set = set()
        k_A = len(A)
        k_B = len(B)

        def dfs_A(val):
            num = 0
            for i in range(k_A):
                if (val >> i) & 1:
                    num += A[i]
            return num

        def dfs_B(val):
            num = 0
            for i in range(k_B):
                if (val >> i) & 1:
                    num += B[i]
            return num

        for val in range(1, (1 << k_A) - 1):
            a_set.add(dfs_A(val))
        for val in range((1 << k_B) - 1):
            b_set.add(dfs_B(val))
        for val in a_set:
            if - val in b_set:
                return True

        num_A = dfs_A((1 << k_A) - 1)
        if - num_A in b_set:
            return True
        num_B = dfs_B((1 << k_B) - 1)
        if - num_B in a_set:
            return True
        return False


data = Solution()
nums = [1, 2, 3, 4, 5, 6, 7, 8]
print(data.splitArraySameAverage(nums))
nums = [3, 1]
print(data.splitArraySameAverage(nums))
